package MonotonicStack;

import java.util.LinkedList;

/**
 * 滑动窗口时刻可以获取窗口中的最小值和最大值
 *
 * @author Liaorun
 */
public class SlidingWindowMaxArray {

    public static void main(String[] args) {
        int[] ints = {4, 2, 3, 5, 6};

        WindowMax windowMax = new WindowMax(ints);
        for (int i = 0; i < 4; i++) {
            windowMax.addNumFromRight();
        }

        for (int i = 0; i < 3; i++) {
            System.out.println(windowMax.getMax());
            windowMax.removeNumFromLeft();
        }
    }

    public static class WindowMax {
        private int L;
        private int R;
        private int[] arr;

        private LinkedList<Integer> qmax;


        public WindowMax(int[] a) {
            L = -1;
            R = 0;
            this.arr = a;
            this.qmax = new LinkedList<>();
        }


        public void addNumFromRight() {
            if (R == arr.length) {
                return;
            }

            // 将所有比当前值要小的值全部从队尾弹出
            while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {
                qmax.pollLast();
            }

            // 添加当前值的坐标
            qmax.addLast(R);

            R++;
        }

        public void removeNumFromLeft() {
            // 左指针不能 >= 右指针的位置
            if (L >= R - 1) {
                return;
            }
            L++;

            if (qmax.peekFirst() == L) {
                qmax.pollFirst();
            }
        }


        /**
         * 获取第一个值，即使窗口中的最大值
         *
         * @return
         */
        public Integer getMax() {
            if (!qmax.isEmpty()) {
                return arr[qmax.peekFirst()];
            }

            return null;
        }
    }


    public static int[] getMaxWindow(int[] arr, int w) {
        if (arr == null || w < 1 || arr.length < w) {
            return null;
        }

        LinkedList<Integer> qmax = new LinkedList<>();

        int[] res = new int[arr.length - w + 1];

        int index = 0;

        for (int i = 0; i < arr.length; i++) {

            // 将所有比当前值要小的值全部从队尾弹出
            while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) {
                qmax.peekLast();
            }

            // 添加当前值的坐标
            qmax.addLast(i);

            // i - w 过期的下标
            if (qmax.peekFirst() == i - w) {
                // 过期的是最大值就弹出该值
                qmax.pollFirst();
            }

            // 窗口形成
            if (i >= w - 1) {
                res[index++] = arr[qmax.peekFirst()];
            }
        }

        return res;
    }

}
